{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #打地鼠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaximumNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打地鼠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「打地鼠」。\n",
    "![middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png](https://pic.leetcode-cn.com/1650273183-nZIijm-middle_img_v2_d5d09656-0616-4a80-845e-ece461c5ba9g.png){:height=\"200px\"}\n",
    "勇者面前有一个大小为 `3*3` 的打地鼠游戏机，地鼠将随机出现在各个位置，`moles[i] = [t,x,y]` 表示在第 `t` 秒会有地鼠出现在 `(x,y)` 位置上，并于第 `t+1` 秒该地鼠消失。\n",
    "\n",
    "勇者有一把可敲打地鼠的锤子，初始时刻（即第 `0` 秒）锤子位于正中间的格子 `(1,1)`，锤子的使用规则如下：\n",
    "- 锤子每经过 `1` 秒可以往上、下、左、右中的一个方向移动一格，也可以不移动\n",
    "- 锤子只可敲击所在格子的地鼠，**敲击不耗时**\n",
    "\n",
    "请返回勇者**最多**能够敲击多少只地鼠。\n",
    "\n",
    "**注意：** \n",
    "- 输入用例保证在相同时间相同位置最多仅有一只地鼠\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入： `moles = [[1,1,0],[2,0,1],[4,2,2]]`\n",
    ">\n",
    ">输出： `2`\n",
    ">\n",
    ">解释：\n",
    ">第 0 秒，锤子位于 (1,1)\n",
    ">第 1 秒，锤子移动至 (1,0) 并敲击地鼠\n",
    ">第 2 秒，锤子移动至 (2,0)\n",
    ">第 3 秒，锤子移动至 (2,1)\n",
    ">第 4 秒，锤子移动至 (2,2) 并敲击地鼠\n",
    ">因此勇者最多可敲击 2 只地鼠\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`moles = [[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：\n",
    ">第 0 秒，锤子位于 (1,1)\n",
    ">第 1 秒，锤子移动至 (2,1) 并敲击地鼠\n",
    ">第 2 秒，锤子移动至 (1,1)\n",
    ">第 3 秒，锤子移动至 (1,0)\n",
    ">第 4 秒，锤子在 (1,0) 不移动并敲击地鼠\n",
    ">第 5 秒，锤子移动至 (2,0) 并敲击地鼠\n",
    ">因此勇者最多可敲击 3 只地鼠\n",
    "\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`moles = [[0,1,0],[0,0,1]]`\n",
    ">\n",
    ">输出：`0`\n",
    ">\n",
    ">解释：\n",
    ">第 0 秒，锤子初始位于 (1,1)，此时并不能敲击 (1,0)、(0,1) 位置处的地鼠\n",
    "\n",
    "\n",
    "**提示：**\n",
    "+ `1 <= moles.length <= 10^5`\n",
    "+ `moles[i].length == 3`\n",
    "+ `0 <= moles[i][0] <= 10^9`\n",
    "+ `0 <= moles[i][1], moles[i][2] < 3`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ZbAuEH](https://leetcode.cn/problems/ZbAuEH/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ZbAuEH](https://leetcode.cn/problems/ZbAuEH/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[2,0,1],[4,2,2]]', '[[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]', '[[2,0,2],[6,2,0],[4,1,0],[2,2,2],[3,0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "      moles.sort()\n",
    "      cur = 0\n",
    "      while moles[0][0] == 0:\n",
    "        if moles[0][1] == 1 and moles[0][2] == 1:\n",
    "          cur = 1\n",
    "        moles.pop(0)\n",
    "      n = len(moles)\n",
    "      dp = [0 for _ in range(n)]\n",
    "\n",
    "      for x in range(n):\n",
    "        i = x\n",
    "        if abs(moles[i][1]-1)+abs(moles[i][2]-1) <= moles[i][0]:\n",
    "            dp[i] = 1\n",
    "        while i >= 0 and i > x-10:\n",
    "          if moles[i][0] < moles[x][0]:\n",
    "            if abs(moles[x][1]-moles[i][1])+abs(moles[x][2]-moles[i][2]) <= moles[x][0]-moles[i][0]:\n",
    "              dp[x] = max(dp[x],dp[i]+1)\n",
    "          i-= 1\n",
    "      \n",
    "      ans = 0\n",
    "      i = n-1\n",
    "      print(dp)\n",
    "      while i >= 0 and moles[i][0] >= moles[n-1][0]-4:\n",
    "        ans = max(ans,dp[i])\n",
    "        i-= 1\n",
    "      return ans+cur\n",
    "\n",
    "          \n",
    "          \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        times = sorted(set([m[0] for m in moles]))\n",
    "        moles.sort()\n",
    "        dp = [-10] * 9\n",
    "        dp[4] = 0\n",
    "        moles.sort()\n",
    "        t0, i = 0, 0\n",
    "        mps = [ [[0],[1],[2],[3],[4],[5],[6],[7],[8]],\n",
    "            [[0, 1, 3], [0, 1, 2, 4], [1, 2, 5], [0, 3, 4, 6], [1, 3, 4, 5, 7], [2, 4, 5, 8], [3, 6, 7], [4, 6, 7, 8], [5, 7, 8]], \n",
    "            [[0, 1, 2, 3, 4, 6], [0, 1, 2, 3, 4, 5, 7], [0, 1, 2, 4, 5, 8], [0, 1, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 7, 8], [0, 3, 4, 6, 7, 8], [1, 3, 4, 5, 6, 7, 8], [2, 4, 5, 6, 7, 8]],\n",
    "            [[0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8]]]\n",
    "\n",
    "        for t in times:\n",
    "            ndp = [-10] * 9\n",
    "            if t - t0 <= 3:\n",
    "                for j in range(9):\n",
    "                    ndp[j] = max([dp[k] for k in mps[t - t0][j]])\n",
    "            else:\n",
    "                ndp = [max(dp)] * 9\n",
    "            while i < len(moles) and moles[i][0] == t:\n",
    "                _, r, c = moles[i]\n",
    "                ndp[r * 3 + c] += 1\n",
    "                i += 1\n",
    "            dp = ndp\n",
    "            t0 = t\n",
    "            # if len(moles) == 6:\n",
    "            # print(t, dp)\n",
    "        return max(dp)#[0]#max(max(v) for v in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "      moles.sort()\n",
    "      cur = 0\n",
    "      while moles[0][0] == 0:\n",
    "        if moles[0][1] == 1 and moles[0][2] == 1:\n",
    "          cur = 1\n",
    "        moles.pop(0)\n",
    "      n = len(moles)\n",
    "      dp = [0 for _ in range(n)]\n",
    "\n",
    "      for x in range(n):\n",
    "        i = x\n",
    "        if abs(moles[i][1]-1)+abs(moles[i][2]-1) <= moles[i][0]:\n",
    "            dp[i] = 1\n",
    "        while i >= 0 and i > x-45:\n",
    "          if moles[i][0] < moles[x][0]:\n",
    "            if abs(moles[x][1]-moles[i][1])+abs(moles[x][2]-moles[i][2]) <= moles[x][0]-moles[i][0]:\n",
    "              dp[x] = max(dp[x],dp[i]+1)\n",
    "          i-= 1\n",
    "      \n",
    "      ans = 0\n",
    "      i = n-1\n",
    "      print(dp)\n",
    "      while i >= 0 and moles[i][0] >= moles[n-1][0]-4:\n",
    "        ans = max(ans,dp[i])\n",
    "        i-= 1\n",
    "      return ans+cur\n",
    "\n",
    "          \n",
    "          \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "      moles.sort()\n",
    "      cur = 0\n",
    "      while moles[0][0] == 0:\n",
    "        if moles[0][1] == 1 and moles[0][2] == 1:\n",
    "          cur = 1\n",
    "        moles.pop(0)\n",
    "      n = len(moles)\n",
    "      dp = [0 for _ in range(n)]\n",
    "\n",
    "      for x in range(n):\n",
    "        i = x\n",
    "        if abs(moles[i][1]-1)+abs(moles[i][2]-1) <= moles[i][0]:\n",
    "            dp[i] = 1\n",
    "        while i >= 0 and i > x-30:\n",
    "          if moles[i][0] < moles[x][0]:\n",
    "            if abs(moles[x][1]-moles[i][1])+abs(moles[x][2]-moles[i][2]) <= moles[x][0]-moles[i][0]:\n",
    "              dp[x] = max(dp[x],dp[i]+1)\n",
    "          i-= 1\n",
    "      \n",
    "      ans = 0\n",
    "      i = n-1\n",
    "      print(dp)\n",
    "      while i >= 0 and moles[i][0] >= moles[n-1][0]-4:\n",
    "        ans = max(ans,dp[i])\n",
    "        i-= 1\n",
    "      return ans+cur\n",
    "\n",
    "          \n",
    "          \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    if g[j] + 1 > f[i]:\n",
    "                        f[i] = g[j] + 1\n",
    "                    # f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                    # f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            if f[i] > ans:\n",
    "                ans = f[i]\n",
    "            # ans = max(ans, f[i])\n",
    "            if f[i] > g[i - 1]:\n",
    "                g[i] = f[i]\n",
    "            else:\n",
    "                g[i] = g[i - 1]\n",
    "            # g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = [[0,1,1]]\n",
    "        flag = False\n",
    "        for mole in sorted(moles):\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        # A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        # A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = 0\n",
    "                if A[i][1] - A[j][1] > 0:\n",
    "                    d += A[i][1] - A[j][1]\n",
    "                else:\n",
    "                    d -= A[i][1] - A[j][1]\n",
    "                \n",
    "                if A[i][2] - A[j][2] > 0:\n",
    "                    d += A[i][2] - A[j][2]\n",
    "                else:\n",
    "                    d -= A[i][2] - A[j][2]\n",
    "\n",
    "                # d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    if g[j] + 1 > f[i]:\n",
    "                        f[i] = g[j] + 1\n",
    "                    # f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                    # f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            if f[i] > ans:\n",
    "                ans = f[i]\n",
    "            # ans = max(ans, f[i])\n",
    "            if f[i] > g[i - 1]:\n",
    "                g[i] = f[i]\n",
    "            else:\n",
    "                g[i] = g[i - 1]\n",
    "            # g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "            ans = max(ans, f[i])\n",
    "            g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            ans = max(ans, f[i])\n",
    "            g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = 0\n",
    "                if A[i][1] - A[j][1] > 0:\n",
    "                    d += A[i][1] - A[j][1]\n",
    "                else:\n",
    "                    d -= A[i][1] - A[j][1]\n",
    "                \n",
    "                if A[i][2] - A[j][2] > 0:\n",
    "                    d += A[i][2] - A[j][2]\n",
    "                else:\n",
    "                    d -= A[i][2] - A[j][2]\n",
    "\n",
    "                # d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    if g[j] + 1 > f[i]:\n",
    "                        f[i] = g[j] + 1\n",
    "                    # f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                    # f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            if f[i] > ans:\n",
    "                ans = f[i]\n",
    "            # ans = max(ans, f[i])\n",
    "            if f[i] > g[i - 1]:\n",
    "                g[i] = f[i]\n",
    "            else:\n",
    "                g[i] = g[i - 1]\n",
    "            # g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        moles.sort()\n",
    "        A = [[0,1,1]]\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        # A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        # A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = 0\n",
    "                if A[i][1] - A[j][1] > 0:\n",
    "                    d += A[i][1] - A[j][1]\n",
    "                else:\n",
    "                    d -= A[i][1] - A[j][1]\n",
    "                \n",
    "                if A[i][2] - A[j][2] > 0:\n",
    "                    d += A[i][2] - A[j][2]\n",
    "                else:\n",
    "                    d -= A[i][2] - A[j][2]\n",
    "\n",
    "                # d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    if g[j] + 1 > f[i]:\n",
    "                        f[i] = g[j] + 1\n",
    "                    # f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                    # f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            if f[i] > ans:\n",
    "                ans = f[i]\n",
    "            # ans = max(ans, f[i])\n",
    "            if f[i] > g[i - 1]:\n",
    "                g[i] = f[i]\n",
    "            else:\n",
    "                g[i] = g[i - 1]\n",
    "            # g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "            # for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = 0\n",
    "                if A[i][1] - A[j][1] > 0:\n",
    "                    d += A[i][1] - A[j][1]\n",
    "                else:\n",
    "                    d -= A[i][1] - A[j][1]\n",
    "                \n",
    "                if A[i][2] - A[j][2] > 0:\n",
    "                    d += A[i][2] - A[j][2]\n",
    "                else:\n",
    "                    d -= A[i][2] - A[j][2]\n",
    "\n",
    "                # d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    if g[j] + 1 > f[i]:\n",
    "                        f[i] = g[j] + 1\n",
    "                    # f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                    # f[i] = max(f[i], f[j] + 1)\n",
    "                j -= 1\n",
    "            if f[i] > ans:\n",
    "                ans = f[i]\n",
    "            # ans = max(ans, f[i])\n",
    "            if f[i] > g[i - 1]:\n",
    "                g[i] = f[i]\n",
    "            else:\n",
    "                g[i] = g[i - 1]\n",
    "            # g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        A = []\n",
    "        flag = False\n",
    "        for mole in moles:\n",
    "            if mole[0] == 0:\n",
    "                if mole[1] == 1 and mole[2] == 1:\n",
    "                    flag = True\n",
    "            else:\n",
    "                A.append(mole)\n",
    "        A.append([0, 1, 1])\n",
    "\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        f = [0] * n\n",
    "        g = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            f[i] = -1e8\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                t = A[i][0] - A[j][0]\n",
    "                d = abs(A[i][1] - A[j][1]) + abs(A[i][2] - A[j][2])\n",
    "                if t > 4:\n",
    "                    f[i] = max(f[i], g[j] + 1)\n",
    "                    break\n",
    "                elif d <= t:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "            ans = max(ans, f[i])\n",
    "            g[i] = max(g[i - 1], f[i])\n",
    "        return ans + int(flag)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        def lcp57(moles):\n",
    "            def possible(l1,l2):\n",
    "                return abs(l2[1]-l1[1])+abs(l2[2]-l1[2])<=l2[0]-l1[0]\n",
    "            moles.sort(key=lambda x:x[0])\n",
    "            n=len(moles)\n",
    "            # 打到第j个，能打到的最大值\n",
    "            c=[1 if possible([0,1,1],moles[i]) else 0 for i in range(n)]\n",
    "            # 考虑到j，最大的c[j]\n",
    "            max_c=[c[0] for i in range(n)]\n",
    "\n",
    "            for j in range(1,n):\n",
    "                max_time=max(abs(moles[j][1]-0),abs(moles[j][1]-2))+max(abs(moles[j][2]-0),abs(moles[j][2]-2))\n",
    "                for i in range(j-1,-1,-1):\n",
    "                    if moles[j][0]==moles[i][0] or c[i]==0:continue\n",
    "                    if moles[j][0]-moles[i][0]>max_time:\n",
    "                        c[j]=max(c[j],max_c[i]+1)\n",
    "                        break\n",
    "                    if possible(moles[i],moles[j]):c[j]=max(c[i]+1,c[j])\n",
    "                max_c[j]=max(max_c[j-1],c[j])\n",
    "            return max_c[-1]\n",
    "        return lcp57(moles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        times = sorted(set([m[0] for m in moles]))\n",
    "        moles.sort()\n",
    "        dp = [-10] * 9\n",
    "        dp[4] = 0\n",
    "        moles.sort()\n",
    "        t0, i = 0, 0\n",
    "        mps = [[[0],[1],[2],[3],[4],[5],[6],[7],[8]],\n",
    "            [[0, 1, 3], [0, 1, 2, 4], [1, 2, 5], [0, 3, 4, 6], [1, 3, 4, 5, 7], [2, 4, 5, 8], [3, 6, 7], [4, 6, 7, 8], [5, 7, 8]], \n",
    "            [[0, 1, 2, 3, 4, 6], [0, 1, 2, 3, 4, 5, 7], [0, 1, 2, 4, 5, 8], [0, 1, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 7, 8], [0, 3, 4, 6, 7, 8], [1, 3, 4, 5, 6, 7, 8], [2, 4, 5, 6, 7, 8]],\n",
    "            [[0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [0, 1, 3, 4, 5, 6, 7, 8], [0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8]]]\n",
    "\n",
    "        for t in times:\n",
    "            ndp = [0] * 9\n",
    "            if t - t0 <= 3:\n",
    "                for j in range(9):\n",
    "                    ndp[j] = max([dp[k] for k in mps[t - t0][j]])\n",
    "            else:\n",
    "                ndp = [max(dp)] * 9\n",
    "            while i < len(moles) and moles[i][0] == t:\n",
    "                _, r, c = moles[i]\n",
    "                ndp[r * 3 + c] += 1\n",
    "                i += 1\n",
    "            dp = ndp\n",
    "            t0 = t\n",
    "            # if len(moles) == 6:\n",
    "            # print(t, dp)\n",
    "        return max(dp)#[0]#max(max(v) for v in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线性DP\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        n = len(moles)\n",
    "        mos = sorted(set(t for t, _, _ in moles) | {0})\n",
    "        m = len(mos)\n",
    "        a = set((t, x, y) for t, x, y in moles)\n",
    "\n",
    "        f = [[-10 ** 9] * 3 for _ in range(3)]\n",
    "        if (0, 1, 1) in a:\n",
    "            f[1][1] = 1\n",
    "        else:\n",
    "            f[1][1] = 0\n",
    "\n",
    "        for k in range(1, m):\n",
    "            t = mos[k]\n",
    "            d = t - mos[k - 1]\n",
    "            g = [[-10 ** 9] * 3 for _ in range(3)]\n",
    "            mx = max(max(r) for r in f)\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    p = int((t, i, j) in a)\n",
    "                    if d >= 4:  # 这个优化能让tle变ac就离谱  10s->4s\n",
    "                        g[i][j] = mx + p\n",
    "                    else:\n",
    "                        for x in range(3):\n",
    "                            for y in range(3):\n",
    "                                dis = abs(x - i) + abs(y - j)\n",
    "                                if dis <= d and g[i][j] < f[x][y] + p:\n",
    "                                    g[i][j] = f[x][y] + p\n",
    "            f = g\n",
    "        return max([max(r) for r in f])\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        moles.sort()\n",
    "        res = [[-999999 for j in range(3)] for i in range(3)]\n",
    "        res[1][1] = 0\n",
    "        show_by_t = [[[0 for j in range(3)] for i in range(3)]]\n",
    "        times = [0]\n",
    "        last_t = 0\n",
    "        for ti,x,y in moles:\n",
    "            if ti == last_t:\n",
    "                show_by_t[-1][x][y] = 1\n",
    "            else:\n",
    "                last_t = ti\n",
    "                times.append(ti)\n",
    "                show_by_t.append([[0 for j in range(3)] for i in range(3)])\n",
    "                show_by_t[-1][x][y] = 1\n",
    "\n",
    "        # for v in show_by_t:\n",
    "        #     print(v)\n",
    "\n",
    "        last_t = 0\n",
    "        for i in range(len(times)):\n",
    "            dt = times[i] - last_t\n",
    "            new_res = [[res[i][j] for j in range(3)] for i in range(3)]\n",
    "            for fx in range(3):\n",
    "                for fy in range(3):\n",
    "                    for nx in range(3):\n",
    "                        for ny in range(3):\n",
    "                            if dt < 4:\n",
    "                                need_dt = 0\n",
    "                                need_dt += fx - nx if fx - nx > 0 else nx - fx\n",
    "                                need_dt += fy - ny if fy - ny > 0 else ny - fy\n",
    "                                if need_dt > dt:\n",
    "                                    continue\n",
    "                            # add = 0\n",
    "                            # if show_by_t[i][nx][ny] == 1:\n",
    "                            #     add = 1\n",
    "                            if res[fx][fy] +  show_by_t[i][nx][ny] > new_res[nx][ny]:\n",
    "                                new_res[nx][ny] =  res[fx][fy] +  show_by_t[i][nx][ny]\n",
    "                            # new_res[nx][ny] = max(new_res[nx][ny], res[fx][fy] + add)\n",
    "            res = new_res\n",
    "            last_t = times[i]\n",
    "            \n",
    "            # print(\"time:\",times[i])\n",
    "            # for v in res:\n",
    "            #     print(v)\n",
    "            # print(\"----------------\")\n",
    "\n",
    "        return max([max(v) for v in res])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        moles.sort()\n",
    "        res = [[-999999 for j in range(3)] for i in range(3)]\n",
    "        res[1][1] = 0\n",
    "        show_by_t = [[[0 for j in range(3)] for i in range(3)]]\n",
    "        times = [0]\n",
    "        last_t = 0\n",
    "        for ti,x,y in moles:\n",
    "            if ti == last_t:\n",
    "                show_by_t[-1][x][y] = 1\n",
    "            else:\n",
    "                last_t = ti\n",
    "                times.append(ti)\n",
    "                show_by_t.append([[0 for j in range(3)] for i in range(3)])\n",
    "                show_by_t[-1][x][y] = 1\n",
    "\n",
    "        # for v in show_by_t:\n",
    "        #     print(v)\n",
    "\n",
    "        last_t = 0\n",
    "        for i in range(len(times)):\n",
    "            dt = times[i] - last_t\n",
    "\n",
    "            if dt >= 4:\n",
    "                max_res = max([max(v) for v in res])\n",
    "                new_res = [[max_res + show_by_t[i][ii][jj] for jj in range(3)] for ii in range(3)]\n",
    "            else:\n",
    "                new_res = [[res[ii][jj] for jj in range(3)] for ii in range(3)]\n",
    "                for fx in range(3):\n",
    "                    for fy in range(3):\n",
    "                        for nx in range(3):\n",
    "                            for ny in range(3):\n",
    "                                if dt < 4:\n",
    "                                    need_dt = 0\n",
    "                                    need_dt += fx - nx if fx - nx > 0 else nx - fx\n",
    "                                    need_dt += fy - ny if fy - ny > 0 else ny - fy\n",
    "                                    if need_dt > dt:\n",
    "                                        continue\n",
    "                                if res[fx][fy] +  show_by_t[i][nx][ny] > new_res[nx][ny]:\n",
    "                                    new_res[nx][ny] =  res[fx][fy] +  show_by_t[i][nx][ny]\n",
    "            res = new_res\n",
    "            last_t = times[i]\n",
    "            \n",
    "\n",
    "        return max([max(v) for v in res])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        moles.sort(key = lambda x:x[0])\n",
    "        n = len(moles)\n",
    "        # dp[i][j]表示当我们遇见第i个地鼠时,且锤子位置在j时能够打到的最大地鼠个数,\n",
    "        dp = [[-float('inf') for _ in range(9)] for _ in range(n + 1)]\n",
    "       \n",
    "        dp[0][4] = 0\n",
    "        pre = 0\n",
    "        d = [[0 for _ in range(9)] for _ in range(9)]\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                d[i][j] = abs(i // 3 - j // 3) + abs(i % 3 - j % 3)\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            t,x,y = moles[i - 1]\n",
    "            diff = t - pre\n",
    "            pre = t     \n",
    "            for last in range(9):\n",
    "                for next_ in range(9):\n",
    "                    if d[last][next_] <= diff:\n",
    "                        dp[i][next_] = max(dp[i][next_],dp[i - 1][last])\n",
    "            dp[i][x * 3 + y] += 1\n",
    "                        \n",
    "            \n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        moles.sort(key = lambda x:x[0])\n",
    "        n = len(moles)\n",
    "        dp = [[-float('inf') for _ in range(9)] for _ in range(n + 1)]\n",
    "       \n",
    "        dp[0][4] = 0\n",
    "        pre = 0\n",
    "        d = [[0 for _ in range(9)] for _ in range(9)]\n",
    "        for i in range(9):\n",
    "            for j in range(9):\n",
    "                d[i][j] = abs(i // 3 - j // 3) + abs(i % 3 - j % 3)\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            t,x,y = moles[i - 1]\n",
    "            diff = t - pre\n",
    "            pre = t     \n",
    "            for last in range(9):\n",
    "                for next_ in range(9):\n",
    "                    if d[last][next_] <= diff:\n",
    "                        dp[i][next_] = max(dp[i][next_],dp[i - 1][last])\n",
    "            dp[i][x * 3 + y] += 1\n",
    "                        \n",
    "            \n",
    "        return max(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            res, t = 0, float('inf')\n",
    "            for j in range(i+1, len(A)):\n",
    "                if A[j][0]-t>=4:\n",
    "                    break\n",
    "                if A[j][0]-A[i][0]>=abs(A[j][1]-A[i][1])+abs(A[j][2]-A[i][2]):\n",
    "                    t = min(t, A[j][0])\n",
    "                    res = max(res, 1+dfs(j))\n",
    "            return res\n",
    "        \n",
    "        A = [[0,1,1]]+sorted(moles)\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            res, t = 0, float('inf')\n",
    "            for j in range(i+1, len(A)):\n",
    "                if A[j][0]-t>=4:\n",
    "                    break\n",
    "                if A[j][0]-A[i][0]>=abs(A[j][1]-A[i][1])+abs(A[j][2]-A[i][2]):\n",
    "                    t = min(t, A[j][0])\n",
    "                    res = max(res, 1+dfs(j))\n",
    "            return res\n",
    "        \n",
    "        A = [[0,1,1]]+sorted(moles)\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "         @lru_cache(None)\n",
    "         def dfs(i):\n",
    "            res, t = 0, float('inf')\n",
    "            for j in range(i+1, len(A)):\n",
    "                if A[j][0]-t>=4:\n",
    "                    break\n",
    "                if A[j][0]-A[i][0]>=abs(A[j][1]-A[i][1])+abs(A[j][2]-A[i][2]):\n",
    "                    t = min(t, A[j][0])\n",
    "                    res = max(res, 1+dfs(j))\n",
    "            return res\n",
    "    \n",
    "         A = [[0,1,1]]+sorted(moles)\n",
    "         return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumNumber(self, moles: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            res, t = 0, float('inf')\n",
    "            for j in range(i+1, len(A)):\n",
    "                if A[j][0]-t>=4:\n",
    "                    break\n",
    "                if A[j][0]-A[i][0]>=abs(A[j][1]-A[i][1])+abs(A[j][2]-A[i][2]):\n",
    "                    t = min(t, A[j][0])\n",
    "                    res = max(res, 1+dfs(j))\n",
    "            return res\n",
    "        \n",
    "        A = [[0,1,1]]+sorted(moles)\n",
    "        return dfs(0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
